# 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。 
# 
#  你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点
# 。 
# 
#  示例 1: 
# 
#  
# 输入: 
# 	Tree 1                     Tree 2                  
#           1                         2                             
#          / \                       / \                            
#         3   2                     1   3                        
#        /                           \   \                      
#       5                             4   7                  
# 输出: 
# 合并后的树:
# 	     3
# 	    / \
# 	   4   5
# 	  / \   \ 
# 	 5   4   7
#  
# 
#  注意: 合并必须从两个树的根节点开始。 
#  Related Topics 树 深度优先搜索 广度优先搜索 二叉树 
#  👍 766 👎 0
import collections
from typing import List


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        if root1 is None:
            return root2
        if root2 is None:
            return root1
        m_node = TreeNode(root1.val + root2.val)
        m_node.left = self.mergeTrees(root1.left, root2.left)
        m_node.right = self.mergeTrees(root1.right, root2.right)
        return m_node


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)
    # 广度优先遍历, 打印树


def log_tree(r: TreeNode):
    if r is None:
        return
    stack = [r]
    while stack:
        node = stack.pop(0)
        log(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)


def tree_list(ro: TreeNode):
    ans = []
    if ro is None:
        return ans
    q = [ro]
    while q:
        node = q.pop(0)
        ans.append(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    return ans


# 深度优先搜索
# 不为空时显性合并, 左右子树递归
#     def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
#         if root1 is None:
#             return root2
#         if root2 is None:
#             return root1
#         merged = TreeNode(root1.val + root2.val)
#         merged.left = self.mergeTrees(root1.left, root2.left)
#         merged.right = self.mergeTrees(root1.right, root2.right)
#         return merged


if __name__ == '__main__':
    s = Solution()
    # 输入:
    # 	Tree 1                     Tree 2
    #           1                         2
    #          / \                       / \
    #         3   2                     1   3
    #        /                           \   \
    #       5                             4   7
    # 输出:
    # 合并后的树:
    # 	     3
    # 	    / \
    # 	   4   5
    # 	  / \   \
    # 	 5   4   7
    t1 = TreeNode(1, TreeNode(3, TreeNode(5)), TreeNode(2))
    t2 = TreeNode(2, TreeNode(1, None, TreeNode(4)), TreeNode(3, None, TreeNode(7)))
    r = s.mergeTrees(t1, t2)
    assert tree_list(r) == [3, 4, 5, 5, 4, 7], tree_list(r)

    # def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
    #     if root1 is None:
    #         return root2
    #     if root2 is None:
    #         return root1
    #     merged = TreeNode(root1.val + root2.val)
    #     queue = collections.deque([merged])
    #     queue1 = collections.deque([root1])
    #     queue2 = collections.deque([root2])
    #     while queue1 and queue2:
    #         node = queue.popleft()
    #         node1 = queue1.popleft()
    #         node2 = queue2.popleft()
    #         left1, right1 = node1.left, node1.right
    #         left2, right2 = node2.left, node2.right
    #         if left1 or left2:
    #             if left1 and left2:
    #                 node_left = TreeNode(left1.val + left2.val)
    #                 node.left = node_left
    #                 queue.append(node_left)
    #                 queue1.append(left1)
    #                 queue2.append(left2)
    #             elif left1:
    #                 node.left = left1
    #             elif left2:
    #                 node.left = left2
    #         if right1 or right2:
    #             if right1 and right2:
    #                 node_right = TreeNode(right1.val + right2.val)
    #                 node.right = node_right
    #                 queue.append(node_right)
    #                 queue1.append(right1)
    #                 queue2.append(right2)
    #             elif right1:
    #                 node.right = right1
    #             elif right2:
    #                 node.right = right2
    #     return merged
